<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>

    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="baidu-site-verification" content="DKi2gJy3XK"/>


        <link rel="shortcut icon" href="/img/favicon.ico">

    <!--Description-->
    
        <meta name="description" content="ZZZXXXCCCWXY999的个人博客，佛系写博客">
    

    <!--Author-->
    
        <meta name="author" content="ZZZXXXCCCWXY999">
    

    <!--Open Graph Title-->
    
        <meta property="og:title" content="红黑树的原理及其底层实现"/>
    

    <!--Open Graph Description-->
    
        <meta property="og:description" content="ZZZXXXCCCWXY999的个人博客，佛系写博客"/>
    

    <!--Open Graph Site Name-->
    <meta property="og:site_name" content="ZZZXXXCCCWXY999的个人博客"/>

    <!--Type page-->
    
        <meta property="og:type" content="article"/>
    

    <!--Page Cover-->
    

    <meta name="twitter:card" content="summary"/>
    

    <!-- Title -->
    
    <title>红黑树的原理及其底层实现 - ZZZXXXCCCWXY999的个人博客</title>

    <!-- Tachyons Core CSS -->
    <link rel="stylesheet" href="/css/tachyons.min.css">
<!--    <link rel="stylesheet" href="https://unpkg.com/tachyons/css/tachyons.min.css">-->

    <!-- Custom Fonts -->
<!--    <link href="/css/font-awesome.min.css" rel="stylesheet" type="text/css">-->
    <link href="//maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">

    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>-->
<!--    <script src="//oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>-->
    <script src="/js/html5shiv.js"></script>
<!--    <script src="//oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>-->
    <script src="/js/respond.min.js"></script>
    <![endif]-->

    <!-- Custom CSS -->
    
<link rel="stylesheet" href="/css/style.css">


    <!-- Google Analytics -->
    


<meta name="generator" content="Hexo 4.2.0"></head>


<body>

<!-- Main Content -->
<!-- Banner -->
<!-- Banner -->
<div class="w-100 bg-1 ph5-ns ph3 text-light">
    
    <nav class="db dt-l w-100 mw8 center border-box pv3">
        <a class="db dtc-l v-mid link dim w-100 w-25-l tc tl-l mb2 mb0-l white" href="/" title="ZZZXXXCCCWXY999的个人博客">
            <img src="http://www.codeblocq.com/assets/projects/hexo-theme-anodyne/assets/anodyne.svg" class="dib h3" alt="ZZZXXXCCCWXY999的个人博客">
        </a>
        <div class="db dtc-l v-mid w-100 w-75-l tc tr-l">
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/" 
                    title="首页">
                    首页
                </a>
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/archives" 
                    title="博客列表">
                    博客列表
                </a>
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/tags" 
                    title="标签">
                    标签
                </a>
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/categories" 
                    title="分类">
                    分类
                </a>
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/about" 
                    title="关于">
                    关于
                </a>
            
                <a class="link dim f6 f5-l dib mr3 mr4-l white" 
                    href="/contact" 
                    title="联系">
                    联系
                </a>
            
        </div>
    </nav>

    <!-- Title -->
    <div class="w-100 mw8 center vh-40 dt">
        <div class="dtc v-mid white">
            <h1 class="f1-l f2-m tc tc-m tl-ns">红黑树的原理及其底层实现</h1>
            <p class="f4 fw3 pab-100px tc tc-m tl-ns">2020-03-10</p>
        </div>
    </div>

    <!-- Icon -->
    <div class="relative w-100 mw8 center white dn dn-m db-ns">
        <i class="header-icon fa fa-file-text-o"></i>
    </div>
</div>

<!-- Content -->
<div class="w-100 ph2 ph4-m ph5-l mv5 mv6-l">
    <div class="content">
        <div class="mw8 center">
            <div class="cf">
                <div class="fl w-100 w-70-l mw7 left fw3 lh-copy pr4-ns pr0-m post-content">
                    <!-- Tags Vertical -->
                    
                        <div class="tags-container-vertical">
                            <div class="tags-sub-container">
                                <a class="fw3 ph1 dib" href="/tags/数据结构/">#数据结构</a> <a class="fw3 ph1 dib" href="/tags/红黑树/">#红黑树</a>
                            </div>
                        </div>
                    

                    <!-- Main Post Content -->
                    <h1 id="红黑树的原理及其底层实现"><a href="#红黑树的原理及其底层实现" class="headerlink" title="红黑树的原理及其底层实现"></a>红黑树的原理及其底层实现</h1><h4 id="红黑树的特点："><a href="#红黑树的特点：" class="headerlink" title="红黑树的特点："></a>红黑树的特点：</h4><p>1.每个节点不是红色就是黑色<br>2.不可能有连在一起的红色节点<br>3.根结点都是黑色<br>4.每个红色节点的子节点都是黑色<br>5.叶子节点都是黑色的空节点<br>6.从任意节点到其每个叶子的所有路径都包含相同的黑色节点。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">RedBlackTree</span></span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">boolean</span> RED = <span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">boolean</span> BLACK = <span class="keyword">true</span>;</span><br><span class="line">    Object key;</span><br><span class="line">    Object value;</span><br><span class="line">    RedBlackTree left;</span><br><span class="line">    RedBlackTree right;</span><br><span class="line">    RedBlackTree patent;</span><br><span class="line">    <span class="keyword">boolean</span> color=BLACK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="变换规则"><a href="#变换规则" class="headerlink" title="变换规则"></a>变换规则</h4><h5 id="父节点是黑色，插入新节点为红色。解决办法：直接插入就可以了"><a href="#父节点是黑色，插入新节点为红色。解决办法：直接插入就可以了" class="headerlink" title="父节点是黑色，插入新节点为红色。解决办法：直接插入就可以了"></a>父节点是黑色，插入新节点为红色。解决办法：直接插入就可以了</h5><h5 id="父节点为红色，叔叔节点为红色。解决办法：变色"><a href="#父节点为红色，叔叔节点为红色。解决办法：变色" class="headerlink" title="父节点为红色，叔叔节点为红色。解决办法：变色"></a>父节点为红色，叔叔节点为红色。解决办法：变色</h5><p>1.父节点变为黑色。<br>2.叔叔节点变为黑色。<br>3.祖父接待您变为红色。<br>4.吧指针定义到祖父节点设为当前要操作的节点</p>
<h5 id="父节点为红色，叔叔节点为黑色，且当前节点是右子树。解决办法：左旋"><a href="#父节点为红色，叔叔节点为黑色，且当前节点是右子树。解决办法：左旋" class="headerlink" title="父节点为红色，叔叔节点为黑色，且当前节点是右子树。解决办法：左旋"></a>父节点为红色，叔叔节点为黑色，且当前节点是右子树。解决办法：左旋</h5><p><img src="/2020/03/10/%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E5%8E%9F%E7%90%86%E5%8F%8A%E5%85%B6%E5%BA%95%E5%B1%82%E5%AE%9E%E7%8E%B0/rorateleft.gif" alt="rotateLeft"></p>
<p>1.把父节点变为黑色<br>2.把祖父节点变为红色<br>3.以祖父节点旋转</p>
<h5 id="父节点为红色，叔叔节点为黑色，且当前节点是左子树。解决办法：左旋"><a href="#父节点为红色，叔叔节点为黑色，且当前节点是左子树。解决办法：左旋" class="headerlink" title="父节点为红色，叔叔节点为黑色，且当前节点是左子树。解决办法：左旋"></a>父节点为红色，叔叔节点为黑色，且当前节点是左子树。解决办法：左旋</h5><p><img src="/2020/03/10/%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E5%8E%9F%E7%90%86%E5%8F%8A%E5%85%B6%E5%BA%95%E5%B1%82%E5%AE%9E%E7%8E%B0/rorateright.gif" alt="rotateRight"></p>
<p>1.把父节点变为黑色<br>2.把祖父节点变为红色<br>3.以祖父节点旋转</p>

                    
                    <!-- Tags Bottom -->
                    
                        <div class="tags-container-bottom">
                            <i class="fa fa-tag pr3 text-main-color"></i><a class="fw3 ph1 dib" href="/tags/数据结构/">#数据结构</a> <a class="fw3 ph1 dib" href="/tags/红黑树/">#红黑树</a>
                        </div>
                    

                    <!-- Comments -->
                    



                </div>
                <div class="fl w-100 w-30-l center fw3 lh-copy pl4-ns tl black-50">
                    
                    <hr class="dn-l mw4 black-50 mt5" />
                    
                    <!-- Widget 1: About -->
                    <div class="mt5 mt0-l">
    <article class="dt db-l mw8 mw8-m mw5-ns center ml0-l bg-white mv3">
        <div class="dn dtc-m db-l v-mid tc pr4 pr0-l" style="min-width: 6rem;">
            <img src="https://avatars0.githubusercontent.com/u/47167745?s=460&v=4" class="mb4-l br-100 h3 w3 h4-l w4-l dib" title="ZZZXXXCCCWXY999">
        </div>
        <div class="dtc db-l v-mid lh-copy measure center f6 black-50 tj">
            我是ZZZXXXCCCWXY999，这是我的博客。<br>没错，看我的ID就能知道我是一个巨星。<br>我会在博客里写一些我在专业方面的分享。
        </div>
    </article>
</div>

                    <hr class="dn-l mw4 black-50 mt5" />
                    
                    <!-- Widget 2: Categories -->
                    
                        <div class="mt5 tc tl-l">
    <h3>分类</h3>
    
        <p>
            <a href="/categories/java/">java</a>
        </p>
    
</div>


                        <hr class="dn-l mw4 black-50 mt5" />
                    

                    <!-- Widget 3: Recent Posts -->
                    <div class="mt5 tc tl-l">
    <h3>近期文章</h3>
    
        <p>
            <a href="/2020/04/01/%E6%B3%9B%E5%9E%8B%E7%9B%B8%E5%85%B3%E7%9F%A5%E8%AF%86/">泛型相关知识</a>
        </p>
    
        <p>
            <a href="/2020/03/14/String-s-abc-%E5%92%8C-String-s-new-String-abc-%E7%9A%84%E5%8C%BA%E5%88%AB/">String s=&#34;abc&#34; 和 String s=new String(&#34;abc&#34;)的区别</a>
        </p>
    
        <p>
            <a href="/2020/03/11/%E5%B0%8F%E7%B1%B3java%E5%AE%9E%E4%B9%A0%E9%9D%A2%E7%BB%8F/">小米java实习面经</a>
        </p>
    
        <p>
            <a href="/2020/03/11/Spring%E5%88%9D%E5%A7%8B%E5%8C%96%E7%9A%84%E6%AD%A5%E9%AA%A4/">Spring初始化的步骤</a>
        </p>
    
        <p>
            <a href="/2020/03/11/%E5%85%B3%E4%BA%8E%E4%B8%89%E5%A4%A7IO%E7%9A%84%E7%90%86%E8%A7%A3-AIO-BIO-NIO/">关于三大IO的理解:BIO,NIO,AIO</a>
        </p>
    
</div>
                </div>
            </div>
        </div>
    </div>
</div>


<!-- Footer -->
<div class="bg-1 ph2 ph5-ns pv5">
    <div class="mv8">
        <div class="center tc">
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://twitter.com/?lang=en" target="_blank">
                        <i class="fa fa-twitter"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://www.facebook.com/" target="_blank">
                        <i class="fa fa-facebook"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://dribbble.com/" target="_blank">
                        <i class="fa fa-dribbble"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://github.com/ZZZXXXCCCWXY999/" target="_blank">
                        <i class="fa fa-github"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://plus.google.com/" target="_blank">
                        <i class="fa fa-google-plus"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://www.behance.net/" target="_blank">
                        <i class="fa fa-behance"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="https://500px.com/" target="_blank">
                        <i class="fa fa-500px"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="mailto:zzzxxxcccwxy999@gmail.com" target="_blank">
                        <i class="fa fa-envelope"></i>
                    </a>
                </div>
            
                <div class="dib mh3">
                    <a class="f3 f2-ns white dim" href="/#" target="_blank">
                        <i class="fa fa-rss"></i>
                    </a>
                </div>
            
        </div>
        <div class="f6 f5-ns center tc white pt5 fw3">
            2020 KTG知识技术小组 | ZZZXXXCCCWXY999 | 真是一个巨星
        </div>
        
            <!-- 不蒜子统计 -->
            <div style="text-align:center;color:#FFFFFF">
            <span id="busuanzi_container_site_pv">
                本站总访问量<span id="busuanzi_value_site_pv"></span>次
        </span>
                <span class="post-meta-divider">|</span>
<!--                <span id="busuanzi_container_site_uv" style='display:none'>-->
<!--                本站访客数<span id="busuanzi_value_site_uv"></span>人-->
<!--        </span>-->
            </div>
<!--            <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>-->
            <script async src="/js/busuanzi.pure.mini.js"></script>
        

    </div>
</div>

<!-- After Footer -->
<!-- Disqus Comments -->



</body>

</html>